package leetcode_700;

import java.util.ArrayList;
import java.util.List;

import helpclass.TreeNode;

/**
 *@author 周杨 
 *MaximumWidthOfBinaryTree_662 输出一颗二叉树最大宽度 这个宽度可以包含Null
 *describe:用dfs AC 91%
 *see:https://leetcode.com/problems/maximum-width-of-binary-tree/discuss/106654/JavaC++-Very-simple-dfs-solution
 *2018年9月28日 下午1:30:31
 */
public class MaximumWidthOfBinaryTree_662 {
	  public int widthOfBinaryTree(TreeNode root) {
	        return dfs(root, 0, 1, new ArrayList<Integer>(), new ArrayList<Integer>());
	    }
	    
	    public int dfs(TreeNode root, int level, int order, List<Integer> start, List<Integer> end){
	        if(root == null)return 0;
	        if(start.size() == level){
	            start.add(order); end.add(order);
	        }
	        else end.set(level, order);
	        int cur = end.get(level) - start.get(level) + 1;
	        int left = dfs(root.left, level + 1, 2*order, start, end);
	        int right = dfs(root.right, level + 1, 2*order + 1, start, end);
	        return Math.max(cur, Math.max(left, right));
	    }
}
